<font size=18><a href="~audio/Ch20/20fig002.au"><img src="bckgrnds/icons/audio.gif" align=sidebar></a>Figure 20.2 Common functions for all STL containers. (Part 1 of 3).</font><br>
<img src="graphics/ch20/fig2002a.gif" ><br>
</page>
<page>
<font size=18>Figure 20.2 - Common functions for all STL containers. (Part 2 of 3) <img src="graphics/ch20/fig2002b.gif" ></font><br>
</page>
<page>
<font size=18>Figure 20.2 - Common functions for all STL containers. (Part 3 of 3). <img src="graphics/ch20/fig2002c.gif" ></font><br>
<font size=18><a href="~audio/Ch20/20fig004.au"><img src="bckgrnds/icons/audio.gif" align=sidebar></a>Figure 20.4 - Common <b>typedefs</b> found in first-class container. (Part 1 of 2) <img src="graphics/ch20/fig2004a.gif" ></font><br>
</page>
<page>
<font size=18>Figure 20.4 Common <b>typedefs</b> found in first-class container (part 2 of 2).<img src="graphics/ch20/fig2004b.gif" ></font><br>
<font size=18><a href="~audio/Ch20/20fig008.au"><img src="bckgrnds/icons/audio.gif" align=sidebar></a>Figure 20.8 - Iterator types supported by each Standard Library container.</font><br>
<img src="graphics/ch20/fig20008.gif" ><br>
</page>
<page>
<font size=18><a href="~audio/Ch20/20fig010.au"><img src="bckgrnds/icons/audio.gif" align=sidebar></a>Figure 20.10 - Iterator operations for each type of iterator. (Part 1 of 2).</font><br>
<img src="graphics/ch20/fig2010a.gif" ><br>
</page>
<page>
<font size=18>Figure 20.10 - Iterator operations for each type of iterator. (Part 2 of 2). </font><br>
<font size=18><a href="~audio/Ch20/20fig039.au"><img src="bckgrnds/icons/audio.gif" align=sidebar></a>Figure 20.39 - Algorithms not covered in this chapter. (Part 1 of 5).</font><br>
<img src="graphics/ch20/fig2039a.gif" ><br>
</page>
<page>
<font size=18>Figure 20.39 - Algorithms not covered in this chapter. (Part 2 of 5).</font><br>
<img src="graphics/ch20/fig2039b.gif" ><br>
</page>
<page>
<font size=18>Figure 20.39 - Algorithms not covered in this chapter. (Part 3 of 5).</font><br>
<img src="graphics/ch20/fig2039c.gif" ><br>
</page>
<page>
<font size=18>Figure 20.39 - Algorithms not covered in this chapter. (Part 4 of 5).</font><br>
<img src="graphics/ch20/fig2039d.gif" ><br>
</page>
<page>
<font size=18>Figure 20.39 - Algorithms not covered in this chapter. (Part 5 of 5). </font><br>
<img src="graphics/ch20/fig2039e.gif" ><br>
</page>
<page>
<font size=18><a href="~audio/Ch20/20fig041.au"><img src="bckgrnds/icons/audio.gif" align=sidebar></a>Figure 20.41 - Function objects in the Standard Library.<tt><b></b></tt> <img src="graphics/ch20/fig20041.gif" ></font><br>
</page>
</section>
<section type=Popup name=Answers title="Answers">
<page pagename="Answer 20.1">
<b>Answer 20.1</b><br>
False. These were avoided for performance reasons.<br>
(T/F) The STL makes abundant use of inheritance and <b>virtual</b> functions.<br>
<foreign name="answers" url="^Answers::c:s0p0">
</page>
<page pagename="Exercise 20.2">
<b>Exercise 20.2</b><br>
The two types of STL containers are sequence containers and <tt><b>________</b></tt>
containers.<br>
<foreign name="answers" url="^Answers::c:s0p1">
</page>
<page pagename="Exercise 20.3">
<b>Exercise 20.3</b><br>
STL avoids using <b>new</b> and <b>delete</b> in favor of using <tt><b>________</b></tt> to enable a
variety of means of controlling memory allocation and deallocation.<br>
<foreign name="answers" url="^Answers::c:s0p2">
</page>
<page pagename="Exercise 20.4">
<b>Exercise 20.4</b><br>
The five main iterator types are <tt><b>________</b></tt>, <tt><b>________</b></tt>, <tt><b>________</b></tt>,
<tt><b>________</b></tt> and <tt><b>________</b></tt>.<br>
<foreign name="answers" url="^Answers::c:s0p3">
</page>
<page pagename="Exercise 20.5">
<b>Exercise 20.5</b><br>
(T/F) A pointer is a generalized form of iterator.<br>
<foreign name="answers" url="^Answers::c:s0p4">
</page>
<page pagename="Exercise 20.6">
<b>Exercise 20.6</b><br>
(T/F) STL algorithms can operate on C-like pointer-based arrays.<br>
<foreign name="answers" url="^Answers::c:s0p5">
</page>
<page pagename="Exercise 20.7">
<b>Exercise 20.7</b><br>
(T/F) STL algorithms are encapsulated as member functions within each
container class.<br>
<foreign name="answers" url="^Answers::c:s0p6">
</page>
<page pagename="Exercise 20.8">
<b>Exercise 20.8</b><br>
(T/F) The <b>remove</b> algorithm does not decrease the size of the <b>vector</b> from which
elements are being removed.<br>
<foreign name="answers" url="^Answers::c:s0p7">
</page>
<page pagename="Exercise 20.9">
<b>Exercise 20.9</b><br>
Memory allocation and deallocation is performed in the STL with <tt><b>________</b></tt>
objects.<br>
<foreign name="answers" url="^Answers::c:s0p8">
</page>
<page pagename="Exercise 20.10">
<b>Exercise 20.10</b><br>
The three STL container adapters are <tt><b>________</b></tt>, <tt><b>________</b></tt>, and
<tt><b>________</b></tt>.<br>
<foreign name="answers" url="^Answers::c:s0p9">
<br>
</page>
<page pagename="Exercise 20.11">
<b>Exercise 20.11</b><br>
(T/F) Container member function <b>end()</b> yields the position of the last element of
the container.<br>
<foreign name="answers" url="^Answers::c:s0p10">
<br>
</page>
<page pagename="Exercise 20.12">
<b>Exercise 20.12</b><br>
STL algorithms operate on container elements indirectly using <tt><b>________</b></tt>.<br>
<foreign name="answers" url="^Answers::c:s0p11">
</page>
<page pagename="Exercise 20.13">
<b>Exercise 20.13</b><br>
The <b>sort</b> algorithm requires a <tt><b>________</b></tt> iterator.<br>
<foreign name="answers" url="^Answers::c:s0p12">
<br>
</page>
<page pagename="Exercise 20.13">
</page>
<page pagename="Exercise 20.14">
<b>Exercise 20.14</b><br>
Write a function template <b>palindrome</b> that takes as a parameter a <b>const</b> <b>vector</b>
and returns <b>true</b> or <b>false</b> depending upon whether the <b>vector</b> does or does not
read the same forwards as backwards (e.g., a <b>vector</b> containing 1, 2, 3, 2, 1 is a
palindrome and a <b>vector</b> containing 1, 2, 3, 4 is not).<br>
<br>
<br>
</page>
<page pagename="Exercise 20.15">
<b>Exercise 20.15</b><br>
Modify the program of <a href="^Code::c:s0p15"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 20.29</a>, the Sieve of Eratosthenes, so that if the
number the user inputs into the program is not prime, the program displays the
prime factors of the number. Remember that a prime number's factors are only 1
and the prime number itself. Every number that is not prime has a unique prime
factorization. For example, consider the number 54. The factors of 54 are 2, 3, 3
and 3. When these values are multiplied together, the result is 54. For the
number 54, the prime factors output should be 2 and 3. <br>
<foreign name="answers" url="^Answers::c:s0p13">
<br>
</page>
<page pagename="Exercise 20.16">
<b>Exercise 20.16</b><br>
Modify <a href="^Exercises::c:s0p15"><img src="bckgrnds/icons/exercise.gif" align=sidebar>Exercise 20.15</a> so that if the number the user inputs into the program is
not prime, the program displays the prime factors of the number and the number
of times that prime factor appears in the unique prime factorization. For
example, the output for the number 54 should be <br>
<font size=2><br></font><font size=11><pre>
The unique prime factorization of 54 is: 2 * 3 * 3 * 3<p>
STL container categories are sequence containers, associative containers, and container adapters. <br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. Sequence and associative containers are referred to as first class containers.">
Container adapters are sometimes referred to as first class containers. <br>
<page pagename="20.1.2 Introduction to Iterators">
outputs an integer to <b>cout</b> by assigning to <b>*outputInt</b>
the sum of <b>number1</b> and <b>number2</b>. Notice the use of
the <a href="^Debug::c:s0p4"><img src="bckgrnds/icons/dbt_ico.gif" align=sidebar></a>dereferencing operator <b>*</b> to use <b>*outputInt</b> as an
<i>lvalue</i> in the assignment statement. If you want to
output another value using <b>outputInt</b>, the <a href="^Errors::c:s0p1"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>iterator must
be incremented with <b>++</b> (both preincrement and
postincrement can be used).<br>
<spacer width=16 height=1><a href="^Illustration::c:s0p10"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 20.6</a> shows the categories of iterators used by
the STL. Each category provides a specific set of
functionality. <br>
<spacer width=16 height=1><a href="^Illustration::c:s0p11"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 20.7</a> illustrates the hierarchy of <a href="^Errors::c:s0p0"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a>iterator
categories. As you follow the hierarchy from top to
bottom, each iterator category supports all the <br>
</page>
<page pagename="20.1.2 Introduction to Iterators">
functionality of the categories above it in the figure.
Thus the "weakest" iterator types are at the top and the
most powerful iterator type is at the bottom. Note that
this is not an inheritance hierarchy.<br>
The category of iterator supported by each container
determines whether that container can be used with
specific algorithms in the STL. Containers that support
random-access iterators can be used with all algorithms
in the STL. As we will see, pointers into arrays may be
used in place of iterators in most STL algorithms,
including those that require random-access iterators.
<a href="^Illustration::c:s0p12"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 20.8</a> shows the category of <a href="^Engineer::c:s0p5"><img src="bckgrnds/icons/seo_ico.gif" align=sidebar></a>iterator supported by
each of the STL containers. Note that only <b>vectors</b>, <br>
</page>
<page pagename="20.1.2 Introduction to Iterators">
<b>deques</b>, <b>lists</b>, <b>sets</b>, <b>multisets</b>, <b>maps</b> and <b>multimaps</b>
(i.e., the first-class containers) are traversable with
iterators.<br>
<spacer width=16 height=1>.<a href="^Illustration::c:s0p15"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 20.9</a> shows the predefined iterator <b>typedefs</b> that
are found in the class definitions of the STL containers.
Not every <b>typedef</b> is defined for every container. We
use <b>const</b> versions of the <a href="^Debug::c:s0p5"><img src="bckgrnds/icons/dbt_ico.gif" align=sidebar></a>iterators for traversing read-
only containers. We use reverse iterators to traverse
containers in the reverse direction.<br>
<spacer width=16 height=1><a href="^Illustration::c:s0p13"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 20.10</a> shows the operations that can be
performed on each iterator type. Note that the
operations for each iterator type include all operations
preceding that type in the figure. Note also that for <br>
</page>
<page pagename="20.1.2 Introduction to Iterators">
input iterators and output iterators it is not possible to
save the iterator, then use the saved value later.<br>
</page>
<page pagename="20.1.2 Introduction to Iterators">
STL first class containers provide member functions begin and end. <br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. Containers that support random access iterators can be used with all STL algorithms.">
Containers that support random access iterators can be used with a limited number of STL algorithms. <br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. An iterator can modify the container element, so it must refer to a modifiable element.">
An object of type iterator is capable of referring to a container element that cannot be modified. <br>
<spacer width=16 height=1><a href="^Illustration::c:s0p16"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 20.11</a> shows many of the <i>mutating-sequence
algorithms</i>--i.e., the algorithms that result in
modifications of the containers to which the algorithms
are applied.<br>
<spacer width=16 height=1><a href="^Illustration::c:s0p17"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 20.12</a> shows many of the nonmutating sequence
algorithms--i.e., the algorithms that do not result in <br>
</page>
<page pagename="20.1.3 Introduction to Algorithms ">
modifications of the containers to which the algorithms
are applied.<br>
<spacer width=16 height=1><a href="^Illustration::c:s0p18"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 20.13</a> shows the numerical algorithms of the
header file <b><numeric></b>.<br>
</page>
<page pagename="20.1.3 Introduction to Algorithms ">
sequence containers--<b>vector</b>, <b>list</b> and <b>deque</b>. Class
<b>vector</b> and class <b>deque</b> both are based on arrays. Class
<b>list</b> implements a linked-list data structure similar to our
<b>List</b> class presented in Chapter 15, but more robust.<br>
<spacer width=16 height=1>One of the most popular containers in the STL is
<b>vector</b>. Class <b>vector</b> is a refinement of the kind of
"smart" <b>Array</b> class we created in Chapter 8. A <b>vector</b>
can change size dynamically. Unlike C and C++ "raw"
arrays (see Chapter 4), <b>vectors</b> can be assigned to one
another. This is not possible with pointer-based, C-like <br>
</page>
<page>
arrays because those array names are constant pointers
and cannot be the targets of assignments. Just as with C
arrays, <b>vector</b> <b><a href="^Perform::c:s0p6"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a></b>subscripting does not perform automatic
range checking, but class <b>vector</b> does provide this
capability (as we will see) via member function <b>at</b>. <br>
<a href="^Illustration::c:s0p4"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 20.2</a> presented the operations common to all the
STL containers. Beyond these operations, each
container typically provides a variety of other
capabilities. Many of these capabilities are common to
several containers. However, these operations are not
always equally efficient for each container.
Programmers must often choose the <a href="^Perform::c:s0p10"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>container most
appropriate for their application. <br>
</page>
<page>
In addition to the common operations described in <a href="^Illustration::c:s0p4"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig.
20.2</a>, the sequence containers have several other
common operations--<b>front</b> to return a reference to the
first element in the <a href="^Perform::c:s0p8"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>container, <b>back</b> to return a
reference to the last element in the container,
<b>push_back</b> to insert a new element at the end of the
container and <b>pop_back</b> to remove the last element of
vector, list, and deque are sequence containers. <br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. vectors can be assigned to each other.">
Like any array, vectors cannot be assigned to each other. <br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. vector subscripting does not provide range checking, but function of class vector does.">
vector subscripting with operator [] provides range checking.at <br>
<component type=button name=b label="Check Your Answer" width=125 height=24>
Class <b>vector</b> provides a data structure with contiguous
memory locations. This enables efficient, direct access
to any element of a vector via the subscript operator <b>[]</b>
exactly like a C or C++ "raw" array. <b><a href="^Perform::c:s0p14"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a></b>Class <b>vector</b> is
most commonly used when the data in the container
must be sorted and easily accessible via a subscript.
When a <b>vector's</b> memory is exhausted, the <b>vector</b>
automatically allocates a larger <a href="^Perform::c:s0p13"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>contiguous area of
memory, copies the original <a href="^Perform::c:s0p12"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>elements into the new
memory and deallocates the old memory.<br>
<spacer width=16 height=1> An important part of every container is the type of
iterator it supports. This determines which algorithms <br>
can be applied to the container. A <b>vector</b> supports
random-access iterators--i.e., all iterator operations
shown in <a href="^Illustration::c:s0p13"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Fig. 20.10</a> can be applied to a <b>vector</b> iterator.
All STL algorithms can operate on a <b>vector</b>. The
iterators for a <b>vector</b> are normally implemented as
pointers to elements of the <b>vector</b>. Each of the STL
algorithms that take iterator arguments requires those
iterators to provide a minimum level of functionality. If
an algorithm requires a forward iterator, for example,
that algorithm can operate on any container that
provides forward iterators, bidirectional iterators or
<spacer width=16 height=1><a href="^Code::c:s0p1"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 20.14</a> illustrates several functions of the <b>vector</b>
class template. Many of these functions are available in
every Standard Library first-class container. You must
include header file <tt><b><vector></b></tt> to use class <b>vector</b>.<br>
Line 15<br>
<font size=2><br></font><font size=11><pre>
vector< int > v;<p>
</pre></font>
declares an instance called <b>v</b> of class <b>vector</b> that stores
<b>int</b> values. When this object is instantiated, an empty
<b>vector</b> is created with a size of 0 (i.e., the number of
elements stored in the <b>vector</b>) and a capacity of 0 (i.e., <br>
<b>output</b> that is attached to <b>cout</b>, so the elements are
copied to the standard output. To use the algorithms of
the Standard Library, you must include the header file
<tt><b><algorithm></b></tt>.<br>
<spacer width=16 height=1>Lines 20 and 21 use functions <b>front</b> and <b>back</b>
(available for all sequence containers) to determine the
first and last <b><a href="^Errors::c:s0p2"><img src="bckgrnds/icons/cpe_ico.gif" align=sidebar></a></b>element of the <b>vector</b>, respectively. <br>
common uses of a <b>deque</b> is to maintain a first-in-first-
out queue of elements. <br>
<spacer width=16 height=1>Additional <a href="^Perform::c:s0p18"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>storage for a <b>deque</b> can be allocated at
either end of the <b>deque</b> in blocks of memory that are
typically maintained as an array of <b><a href="^Perform::c:s0p17"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a></b>pointers to those
blocks. Due to the non-contiguous memory layout of a
<b>deque</b>, a <b>deque</b> iterator must be more intelligent than
the pointers that are used to iterate through <b>vectors</b> or
pointer-based arrays.<br>
<spacer width=16 height=1>Class <b>deque</b> provides the same basic operations as class
<b>vector</b>, but adds member functions <b>push_front</b> and
<b>pop_front</b> to allow insertion and deletion at the
<a href="^Code::c:s0p4"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 20.18</a> demonstrates features of class <b>deque</b>.
Remember that many of the functions presented in <a href="^Code::c:s0p1"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figs.
20.14</a>, <a href="^Code::c:s0p2"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>20.15</a> and <a href="^Code::c:s0p3"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>20.17</a> also can be used with class
<b>deque</b>. Header file <tt><b><deque></b></tt> must be included to use
class <b>deque</b>.<br>
<spacer width=16 height=1>Line 11<br>
<font size=2><br></font><font size=11><pre>
deque< double > values;<p>
</pre></font>
instantiates a <b>deque</b> that can store <b>double</b> values. Lines
14 through 16 use functions <b>push_front</b> and
<b>push_back</b> to insert elements at the beginning and end
of the <b>deque</b>, respectively. Remember that <b>push_back</b>
is available for all sequence containers, but <b>push_front</b>
is only available for class <b>list</b> and class <b>deque</b>.<br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. The header <deque> must be included. Note: Some older C++ compilers that support the STL use header files ending in .">
Header <deque.h> must be included to use deques..h <br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. Function pop_front is only available for list and deque.">
Function pop_front is available for vector, list, and deque. <br>
<component type=button name=b label="Check Your Answer" width=125 height=24>
object <tt><b>less< int ></b></tt>. Duplicate keys are allowed in a
<b>multimap</b>, so multiple values can be associated with a
single key. This is often called a one-to-many
relationship. For example, in a credit-card transaction-
processing system, one credit card account can have
many associated transactions; in a university, one
student can take many courses and one professor can
teach many students; in the military, one rank (like
"private") has many people. A <b>multimap</b> supports
bidirectional iterators (but not random-access iterators).
As with <b>multisets</b> and <b>sets</b>, <b>multimaps</b> are <b><a href="^Perform::c:s0p22"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a></b>typically
implemented as a red-black binary search tree in which
the nodes of the tree are key/value <b>pairs</b>. <a href="^Code::c:s0p7"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 20.21</a> <br>
container. <a href="^Code::c:s0p8"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 20.22</a> uses the same features as <a href="^Code::c:s0p7"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig.
20.21</a> except for the subscript operator. Header file
<tt><b><map></b></tt> must be included to use class <b>map</b>. Lines 29
and 30<br>
<font size=2><br></font><font size=11><pre>
pairs[ 25 ] = 9999.99; <p>
// change existing value for 25<p>
pairs[ 40 ] = 8765.43; <p>
// insert new value for 40<p>
</pre></font>
use the subscript operator of class <b>map</b>. When the
subscript is a key that is already in the <b>map</b>, the <br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. The programmer can choose the underlying data structure of an adapter, but normally the default underlying container specified by the adapter is used.">
The programmer cannot choose the underlying data structure of an adapter. <br>
container), <b>front</b> to get a reference to the first element
in the <b>queue</b> (implemented by <b><a href="^Perform::c:s0p26"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a></b>calling function <b>front</b> of
the underlying container), <b>back</b> to get a reference to the
last element in the <b>queue</b> (implemented by calling
function <b>back</b> of the underlying container), <b>empty</b> to
determine if the <b>queue</b> is empty (implemented by
calling function <b>empty</b> of the <a href="^Perform::c:s0p25"><img src="bckgrnds/icons/perf_ico.gif" align=sidebar></a>underlying container)
and <b>size</b> to get the number of elements in the <b>queue</b>
(implemented by calling function <b>size</b> of the underlying
Until STL, class libraries of containers and algorithms
were essentially incompatible among vendors. Early
container libraries generally used inheritance and
polymorphism, with the associated overhead of <b>virtual</b>
function calls. Early libraries had the algorithms built in
to the container classes as class behaviors. <a href="^Engineer::c:s0p12"><img src="bckgrnds/icons/seo_ico.gif" align=sidebar></a>STL
separates the algorithms from the containers. This
makes it much easier to add new <a href="^Engineer::c:s0p11"><img src="bckgrnds/icons/seo_ico.gif" align=sidebar></a>algorithms. STL is
implemented for efficiency. It avoids the overhead of
<b>virtual</b> function calls. With STL, the elements of
containers are accessed through iterators.<br>
</page>
<page pagename="20.5.1 <b>fill</b>, <b>fill_n</b>, <b>generate</b> and <b>generate_n</b> ">
<b>20.5.1 <b>fill</b>, <b>fill_n</b>, <b>generate</b> and <b>generate_n</b> </b><br>
<b><a href="^Code::c:s0p12"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 20.26</a></b> demonstrates the <b>fill</b>, <b>fill_n</b>, <b>generate</b> and
<b>generate_n</b> Standard Library functions. Functions <b>fill</b>
and <b>fill_n</b> set every element in a range of container
elements to a specific value. Functions <b>generate</b> and
<b>generate_n</b> use a <i>generator function</i> to create values
for every element in a range of container elements. The
generator function takes no arguments and returns a
value that can be placed in an element of the container.<br>
Line 17<br>
<font size=2><br></font><font size=11><pre>
fill( chars.begin(), chars.end(), '5' );<p>
</pre></font>
uses function <b>fill</b> to place the character <b>'5'</b> in every
element of <tt><b>vector chars</b></tt> from <b>chars.begin()</b> up to, but <br>
</page>
<page pagename="20.5.1 <b>fill</b>, <b>fill_n</b>, <b>generate</b> and <b>generate_n</b> ">
not including, <b>chars.end()</b>. Note that the iterators
supplied as the first and second argument must be at
least forward iterators (i.e., they can be used for both
input from a container and output to a container in the
forward direction).<br>
<spacer width=16 height=1>Line 21<br>
<font size=2><br></font><font size=11><pre>
fill_n( chars.begin(), 5, 'A' );<p>
</pre></font>
uses function <b>fill_n</b> to place the character <b>'A'</b> in the first
five elements of <b>vector chars</b>. The iterator supplied as
the first argument must be at least an output iterator
(i.e., it can be used for output to a container in the
forward direction). The second argument specifies the <br>
</page>
<page pagename="20.5.1 <b>fill</b>, <b>fill_n</b>, <b>generate</b> and <b>generate_n</b> ">
number of elements to fill. The third argument specifies
the value to place in each element.<br>
<spacer width=16 height=1>Line 26<br>
<font size=2><br></font><font size=11><pre>
generate( chars.begin(), chars.end(), <p>
nextLetter );<p>
</pre></font>
uses function <b>generate</b> to place the result of a call to
generator function <b>nextLetter</b> in every element of
<b>vector chars</b> from <b>chars.begin()</b> up to, but not
including, <b>chars.end()</b>. The iterators supplied as the
first and second arguments must be at least forward
iterators. Function <b>nextLetter</b> (defined at line 39)
begins with the character <b>'A'</b> maintained in a <b>static</b>
local variable. The statement at line 42<br>
</page>
<page pagename="20.5.1 <b>fill</b>, <b>fill_n</b>, <b>generate</b> and <b>generate_n</b> ">
<font size=2><br></font><font size=11><pre>
return letter++;<p>
</pre></font>
returns the current value of <b>letter</b> each time <b>nextLetter</b>
is called, then increments the value of <b>letter</b>.<br>
<spacer width=16 height=1>Line 30<br>
<font size=2><br></font><font size=11><pre>
generate_n( chars.begin(), 5, nextLetter );<p>
</pre></font>
uses function <b>generate_n</b> to place the result of a call to
generator function <b>nextLetter</b> in five elements of
<b>vector</b> <b>chars</b> starting from <b>chars.begin()</b>. The iterator
supplied as the first argument must be at least an output
iterator.<br>
</page>
<page pagename="20.5.1 <b>fill</b>, <b>fill_n</b>, <b>generate</b> and <b>generate_n</b> ">
<b>Select the true statement(s). </b><br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. The generator function passed to generate_n does not take any arguments and returns a value that can be placed in the container.">
The generator function passed to generate_n takes one argument and does not return a value. <br>
Function random_shuffle randomly changes the order of the elements and takes two random-access iterators as arguments. <br>
<component type="checkbox" width=20 height=18 label="" name="" feedback="False. Function accumulate does sum the values in a sequence, but it is defined in <numeric>.">
Function accumulate sums the values in a sequence and is defined in <algorithm>. <br>
Function find returns an input iterator that is positioned either at the first element containing the value or an iterator indicating the end of sequence. <br>
Combines two sorted ascending sequences of values into a third sorted ascending sequence.<component type="drop" width=112 height=18 name="merge"> <br>
After copying a sequence, returns an iterator positioned at the beginning of a sequence.<component type="drop" width=112 height=18 name="copy_backward"> <br>
Eliminates duplicates in a sequence.<component type="drop" width=112 height=18 name="unique"> <br>
Reverses all elements in a given range.<component type="drop" width=112 height=18 name="reverse"> <br>
<component type=button name=b label="Check Your Answer" width=125 height=24>
</page>
<page pagename="20.5.9 <b>inplace_merge</b>, <b>unique_copy</b> and ">
<b>reverse_copy</b>
<b>20.5.9 <b>inplace_merge</b>, <b>unique_copy</b> and
<b>reverse_copy</b> </b><br>
The program of <a href="^Code::c:s0p20"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 20.34</a> demonstrates Standard
Library functions <tt><b>inplace_merge</b></tt>, <b>unique_copy</b> and
<b>reverse_copy</b>. <br>
Line 22<br>
<font size=2><br></font><font size=11><pre>
inplace_merge( v1.begin(), v1.begin() + 5,<p>
v1.end() );<p>
</pre></font>
uses function <b>inplace_merge</b> to merge two sorted
sequences of elements in the same container. In this
example, the elements from <b>v1.begin()</b> up to, but not
including, <b>v1.begin() + 5</b> are merged with the elements
from <b>v1.begin() + 5 </b>up to, but not including, <b>v1.end()</b>. <br>
</page>
<page pagename="20.5.9 <b>inplace_merge</b>, <b>unique_copy</b> and ">
This function requires its three iterator arguments to be
at least bidirectional iterators. A second version of this
function takes as a fourth argument a binary predicate
function for comparing elements in the two sequences.<br>
<spacer width=16 height=1>Lines 27 and 28<br>
<font size=2><br></font><font size=11><pre>
unique_copy( v1.begin(), v1.end(), <p>
back_inserter( results1 ) );<p>
</pre></font>
uses function <b>unique_copy</b> to make a copy of all the
unique elements in the sorted sequence of values from
<b>v1.begin()</b> up to, but not including, <b>v1.end()</b>. The
copied elements are placed into vector <b>results1</b>. The
first two arguments must be at least input iterators and
the last argument must be at least an output iterator. In <br>
</page>
<page pagename="20.5.9 <b>inplace_merge</b>, <b>unique_copy</b> and ">
this example, we did not pre-allocate enough elements
in <b>results1</b> to store all the elements copied from <b>v1</b>.
Instead, we function <b>back_inserter</b> (defined in header
file <b><iterator></b>) to add elements to the end of <b>vector
v1</b>. The <b>back_inserter</b> uses class <b>vector's</b> capability to
insert elements at the end of the <b>vector</b>. Because the
<b>back_inserter</b> inserts an element rather than replacing
an existing element's value, the <b>vector</b> is able to grow
to accommodate additional elements. A second version
of the <b>unique_copy</b> function takes as a fourth argument
a binary predicate function for comparing elements for
equality.<br>
<spacer width=16 height=1>Lines 34 and 35<br>
</page>
<page pagename="20.5.9 <b>inplace_merge</b>, <b>unique_copy</b> and ">
<font size=2><br></font><font size=11><pre>
reverse_copy( v1.begin(), v1.end(),<p>
back_inserter( results2 ) );<p>
</pre></font>
uses function <b>reverse_copy</b> to make a reversed copy of
the elements in the range <b>v1.begin()</b> up to, but not
including, <b>v1.end()</b>. The copied elements are inserted
into the <b>vector results2</b> using a <b>back_inserter</b> object to
ensure that the <b>vector</b> can grow to accommodate the
appropriate number of elements copied. The
<b>reverse_copy</b> function requires its first two iterator
arguments to be at least bidirectional iterators and its
third iterator argument to be at least an output iterator.<br>
</page>
<page pagename="20.5.9 <b>inplace_merge</b>, <b>unique_copy</b> and ">
<b>Drag the correct term to the box associated with the
Determines the set of sorted values in the first set that are not in the second set of sorted values.<component type="drop" width=136 height=18 name="set_difference"> <br>
Creates a set of all the elements that are in either or both of the two sorted sets.<component type="drop" width=136 height=18 name="set_union"> <br>
Determines the set of values from the first set that are contained in the second set of values.<component type="drop" width=136 height=18 name="set_intersection"> <br>
<component type=button name=b label="Check Your Answer" width=125 height=24>
</page>
<page pagename="20.5.11<tt> <b>lower_bound</b></tt>, <b>upper_bound</b> and ">
<b>equal_range </b>
<b>20.5.11<tt> <b>lower_bound</b></tt>, <b>upper_bound</b> and
<b>equal_range </b> </b><br>
<a href="^Code::c:s0p22"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 20.36</a> demonstrates the <b>lower_bound</b>,
<b>upper_bound</b> and <b>equal_range</b> Standard Library
functions.<br>
Line 21<br>
<font size=2><br></font><font size=11><pre>
lower = lower_bound( v.begin(), v.end(), 6 );<p>
</pre></font>
uses function <b>lower_bound</b> to determine the first
location in a sorted sequence of values at which the
third argument could be inserted in the sequence and
the sequence would still be sorted in ascending order.
The first two iterator arguments must be at least
forward iterators. The third argument is the value for <br>
</page>
<page pagename="20.5.11<tt> <b>lower_bound</b></tt>, <b>upper_bound</b> and ">
which to determine the lower bound. The function
returns a forward iterator pointing to the position at
which the insert can occur. A second version of
function <b>lower_bound</b> takes as a fourth argument a
binary predicate function indicating the order in which
the elements were originally sorted.<br>
<spacer width=16 height=1>Line 26<br>
<font size=2><br></font><font size=11><pre>
upper = upper_bound( v.begin(), v.end(), 6 );<p>
</pre></font>
uses function <b>upper_bound</b> to determine the last
location in a sorted sequence of values at which the
third argument could be inserted in the sequence and
the sequence would still be sorted in ascending order.
The first two iterator arguments must be at least <br>
</page>
<page pagename="20.5.11<tt> <b>lower_bound</b></tt>, <b>upper_bound</b> and ">
forward iterators. The third argument is the value for
which to determine the upper bound. The function
returns a forward iterator pointing to the position at
which the insert can occur. A second version of
function <b>upper_bound</b> takes as a fourth argument a
binary predicate function indicating the order in which
the elements were originally sorted.<br>
<spacer width=16 height=1>Line 31<br>
<font size=2><br></font><font size=11><pre>
eq = equal_range( v.begin(), v.end(), 6 );<p>
</pre></font>
uses function <b>equal_range</b> to return a <b>pair</b> of forward
iterators containing the combined results of performing
both a <b>lower_bound</b> and an <b>upper_bound</b> operation.
The first two iterator arguments must be at least <br>
</page>
<page pagename="20.5.11<tt> <b>lower_bound</b></tt>, <b>upper_bound</b> and ">
forward iterators. The third argument is the value for
which to determine the equal range. The function
returns a <b>pair</b> of forward iterators for the lower bound
(<b>eq.first</b>) and upper bound (<b>eq.second</b>), respectively. <br>
<spacer width=16 height=1>Functions <b>lower_bound</b>, <b>upper_bound</b> and
<b>equal_range</b> are often used to locate insertion points in
sorted sequences. Line 40 uses <b>lower_bound</b> to locate
the first point at which <b>5</b> can be inserted in order in <b>v</b>.
Line 46 uses <b>upper_bound</b> to locate the last point at
which <b>7</b> can be inserted in order in <b>v</b>. Line 52 uses
<b>equal_range</b> to locate the first and last points at which
<b>5</b> can be inserted in order in <b>v</b>.<br>
</page>
<page pagename="20.5.11<tt> <b>lower_bound</b></tt>, <b>upper_bound</b> and ">
<b>Drag the correct term to the box associated with the
Determines the first location in a sorted sequence of values at which an argument can be insertedwhile still maintaining the sorted order.<component type="drop" width=96 height=18 name="lower_bound"> <br>
Determines the last location in a sorted sequence of values at which an argument can be insertedwhile still maintaining the sorted order.<component type="drop" width=96 height=18 name="upper_bound"> <br>
Returns a pair of forward iterators that represent the lower bound and upper bound, respectively.<component type="drop" width=96 height=18 name="equal_range"> <br>
<component type=button name=b label="Check Your Answer" width=125 height=24>
</page>
<page pagename="20.5.12 Heapsort">
<b>20.5.12 Heapsort</b><br>
<a href="^Code::c:s0p23"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 20.37</a> demonstrates the Standard Library
functions for performing the heapsort sorting algorithm.
Heapsort is a sorting algorithm in which an array of
elements is arranged into a special binary tree called a
<i>heap</i>. The key features of a heap are that the largest
element is always at the top of the heap and the values
of the children of any node in the binary tree are always
less than or equal to that node's value. A heap arranged
in this manner is often called a <i>maxheap</i>. Heapsort is
generally discussed in the computer science courses
called "Data Structures" and "Algorithms."<br>
<spacer width=16 height=1>Line 19<br>
</page>
<page pagename="20.5.12 Heapsort">
<font size=2><br></font><font size=11><pre>
make_heap( v.begin(), v.end() );<p>
</pre></font>
uses function <b>make_heap</b> to take a sequence of values
in the range <b>v.begin()</b> up to, but not including, <b>v.end()</b>
and create a heap that can be used to produce a sorted
sequence. The two iterator arguments must be random-
access iterators, so this function will only work with
arrays, <b>vectors</b> and <b>deques</b>. A second version of this
function takes as a third argument a binary predicate
function for comparing values.<br>
<spacer width=16 height=1>Line 22<br>
<font size=2><br></font><font size=11><pre>
sort_heap( v.begin(), v.end() );<p>
</pre></font>
uses function <b>sort_heap</b> to sort a sequence of values in
the range <b>v.begin()</b> up to, but not including, <b>v.end()</b> that <br>
</page>
<page pagename="20.5.12 Heapsort">
are already arranged in a heap. The two iterator
arguments must be random-access iterators. A second
version of this function takes as a third argument a
binary predicate function for comparing values.<br>
Line 32<br>
<font size=2><br></font><font size=11><pre>
push_heap( v2.begin(), v2.end() );<p>
</pre></font>
uses function <b>push_heap</b> to add a new value into a
heap. We take one element of array <tt><b>a</b></tt> at a time, append
that element to the end of <b>vector v2</b> and perform the
<b>push_heap</b> operation. If the appended element is the
only element in the <b>vector</b>, the <b>vector</b> is already a heap.
Otherwise, function <b>push_heap</b> rearranges the
elements of the <b>vector</b> into a heap. Each time <br>
</page>
<page pagename="20.5.12 Heapsort">
<b>push_heap</b> is called, it assumes that the last element
currently in the <b>vector</b> (i.e., the one that is appended
before the <b>push_heap</b> function call) is the element
being added to the heap and that all other elements in
the <b>vector</b> are already arranged as a heap. The two
iterator arguments to <b>push_heap</b> must be random-
access iterators. A second version of this function takes
as a third argument a binary predicate function for
comparing values.<br>
<spacer width=16 height=1>Line 39<br>
<font size=2><br></font><font size=11><pre>
pop_heap( v2.begin(), v2.end() - i );<p>
</pre></font>
uses function <b>pop_heap</b> to remove the top element of
the heap. This function assumes that the elements in the <br>
</page>
<page pagename="20.5.12 Heapsort">
range specified by its two random-access iterator
arguments are already a heap. Repeatedly removing the
top element of a heap eventually results in a sorted
sequence of values. Function <b>pop_heap</b> swaps the first
element of the heap (<b>v2.begin()</b> in this example) with
the last element of the heap (the element before
<b>v2.end() - i</b> in this example), then ensures that the
elements up to, but not including, the last element still
form a heap. Notice in the output that after the
<b>pop_heap</b> operations, the <b>vector</b> is sorted in ascending
order. A second version of this function takes as a third
argument a binary predicate function for comparing
values.<br>
</page>
<page pagename="20.5.12 Heapsort">
<b>Drag the correct term to the box associated with the
Sort a sequence of values in the heap.<component type="drop" width=80 height=18 name="sort_heap"> <br>
Add a new value to the heap.<component type="drop" width=80 height=18 name="push_heap"> <br>
Create a heap that can be used to produce a sorted sequence.<component type="drop" width=80 height=18 name="make_heap"> <br>
Remove the top element of the heap.<component type="drop" width=80 height=18 name="pop_heap"> <br>
<component type=button name=b label="Check Your Answer" width=125 height=24>
</page>
<page pagename="20.5.13<tt> <b>min</b></tt> and <b>max </b> ">
<b>20.5.13<tt> <b>min</b></tt> and <b>max </b> </b><br>
Algorithms <b>min</b> and <b>max</b> determine the minimum of
two elements and the maximum of two elements,
respectively. The program of <a href="^Code::c:s0p24"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Fig. 20.38</a> demonstrates
<b>min</b> and <b>max</b> for <b>int</b> and <b>char</b> values.<br>
</page>
<page pagename="20.5.14 Algorithms Not Covered in this Chapter">
<b>20.5.14 Algorithms Not Covered in this Chapter</b><br>
<a href="^Illustration::c:s0p20"><img src="bckgrnds/icons/ill_ico.gif" align=sidebar>Figure 20.39</a> discusses the algorithms that are not
covered in this chapter. <br>
</page>
</section>
<section type=Body name=Default title="20.6 Class bitset ">
<page>
<font size=18 bold>20.6 Class <b>bitset </b> </font><hr>
Class <b>bitset</b> makes it easy to create and manipulate <i>bit
sets</i>. Bit sets are useful for representing a set of bit
flags. <b>bitsets</b> are fixed in size at compile time. <br>
<font size=2><br></font><font size=11><pre>
bitset< size > b;<p>
</pre></font>
creates <b>bitset b</b> in which every bit is initially <b>0</b>.<br>
<font size=2><br></font><font size=11><pre>
b.set( bitNumber );<p>
</pre></font>
sets bit <b>bitNumber</b> of <b>bitset b</b> "on." The expression
<b>b.set()</b> sets all bits in <b>b</b> "on."<br>
<font size=2><br></font><font size=11><pre>
b.reset( bitNumber );<p>
</pre></font>
</page>
<page>
sets bit <b>bitNumber</b> of <b>bitset b</b> "off." The expression
<b>b.reset()</b> sets all bits in <b>b</b> "off."<br>
<font size=2><br></font><font size=11><pre>
b.flip( bitNumber );<p>
</pre></font>
"flips" bit <b>bitNumber</b> of <b>bitset b</b> (e.g., if the bit is on,
<b>flip</b> sets it off). The expression <b>b.flip()</b> flips all bits in <b>b</b>.<br>
<font size=2><br></font><font size=11><pre>
b[ bitNumber ];<p>
</pre></font>
returns a reference to the bit <b>bitNumber</b> of <b>bitset b</b>.
Similarly, <br>
<font size=2><br></font><font size=11><pre>
b.at( bitNumber );<p>
</pre></font>
performs range checking on <b>bitNumber</b> first. Then, if
<b>bitNumber</b> is in range, <b>at</b> returns a reference to the bit.
Otherwise, <b>at</b> throws an <b>out_of_range</b> exception.<br>
</page>
<page>
<font size=2><br></font><font size=11><pre>
b.test( bitNumber );<p>
</pre></font>
performs range checking on <b>bitNumber</b> first. Then, if
<b>bitNumber</b> is in range, <b>test</b> returns <b>true</b> if the bit is on
and <b>false</b> if the bit is off. Otherwise, <b>test</b> throws an
<b>out_of_range</b> exception.<br>
<spacer width=16 height=1>The expression<br>
<font size=2><br></font><font size=11><pre>
b.size()<p>
</pre></font>
returns the number of bits in <b>bitset b</b>.<br>
<spacer width=16 height=1>The expression<br>
<font size=2><br></font><font size=11><pre>
b.count()<p>
</pre></font>
returns the number of bits that are set in <b>bitset b</b>.<br>
<spacer width=16 height=1>The expression<br>
</page>
<page>
<font size=2><br></font><font size=11><pre>
b.any()<p>
</pre></font>
returns <b>true</b> if any bit is set in <b>bitset b</b>.<br>
<spacer width=16 height=1>The expression<br>
<font size=2><br></font><font size=11><pre>
b.none()<p>
</pre></font>
returns <b>true</b> if none of the bits are set in <b>bitset b</b>.<br>
<spacer width=16 height=1>The expressions<br>
<font size=2><br></font><font size=11><pre>
b == b1<p>
b != b1<p>
</pre></font>
compare the two <b>bitsets</b> for equality and inequality,
respectively.<br>
<spacer width=16 height=1>Each of the bitwise assignment operators <tt><b>&=</b></tt>, <tt><b>|=</b></tt> and <tt><b>^=</b></tt>
can be used to combine <b>bitsets</b>, For example,<br>
</page>
<page>
<font size=2><br></font><font size=11><pre>
b &= b1;<p>
</pre></font>
performs a bit-by-bit logical AND between <b>bitsets b</b>
and <b>b1</b>. The result is stored in <b>b</b>. Bitwise logical OR
and bitwise logical XOR are performed by<br>
<font size=2><br></font><font size=11><pre>
b != b1;<p>
b ^= b2;<p>
</pre></font>
The expression<br>
<font size=2><br></font><font size=11><pre>
b >>= n;<p>
</pre></font>
shifts the bits in <b>bitset b</b> right by <b>n</b> positions.<br>
<spacer width=16 height=1>The expression<br>
<font size=2><br></font><font size=11><pre>
b <<= n;<p>
</pre></font>
shifts the bits in <b>bitset b</b> left by <b>n</b> positions.<br>
</page>
<page>
The expressions<br>
<font size=2><br></font><font size=11><pre>
b.to_string()<p>
b.to_ulong()<p>
</pre></font>
convert <b>bitset b</b> to a <b>string</b> and a <b>long</b>, respectively. <br>
<spacer width=16 height=1><a href="^Code::c:s0p25"><img src="bckgrnds/icons/code_ico.gif" align=sidebar>Figure 20.40</a> revisits the Sieve of Eratosthenes for
finding prime numbers we discussed in Exercise 4.29.
A <b>bitset</b> is used instead of an array to implement the
algorithm. The program displays all the prime numbers
from 2 to 1023 then allows the user to enter a number to
determine if that number is prime.<br>
<spacer width=16 height=1>Line 14 <br>
<font size=2><br></font><font size=11><pre>
bitset< size > sieve;<p>
</pre></font>
</page>
<page>
creates a <b>bitset</b> of <b>size</b> bits (<b>size</b> is 1024 in this
example). We ignore the bits at positions 0 and 1 in this
program. By default, all the bits in the <b>bitset</b> are set
"off." The code<br>
<font size=2><br></font><font size=11><pre>
// perform Sieve of Eratosthenes<p>
int finalBit = sqrt( sieve.size() ) + 1;<p>
for ( i = 2; i < finalBit; ++i ) <p>
if ( sieve.test( i ) ) <p>
for ( int j = 2 * i; j < size; j += i ) <p>
sieve.reset( j );<p>
</pre></font>
determines all the prime numbers from 2 to 1023. The
integer <b>finalBit</b> is used to determine when the
algorithm is complete. The basic algorithm is that a <br>
</page>
<page>
number is prime if it has no divisors other than 1 and
itself. Starting with the number 2, once we know a
number is prime, we can eliminate all multiples of that
number. The number 2 is only divisible by 1 and itself,
so it is prime. Therefore, we can eliminate 4, 6, 8, and
so on. The number 3 is divisible by 1 and itself.
Therefore, we can eliminate all multiples of 3 (keep in
mind that all even numbers have already been
eliminated). <br>
</page>
<page>
<b>Drag the correct term to the box associated with the
<indent width=8 delay>* Using STL can save considerable time and effort,
and result in higher quality programs.</indent>
<indent width=8 delay>* The choice of what Standard Library container to use
in a particular application is often based on performance considerations.</indent>
<indent width=8 delay>* STL containers are all "templatized" so that you can
tailor them to hold the type of data relevant to your particular applications.</indent>
<indent width=8 delay>* STL includes many popular data structures as containers and provides many algorithms that programs use
to process data in these containers.</indent>
</page>
<page>
<indent width=8 delay>* STL containers are in three major categories--
<i>sequence containers</i>, <i>associative containers</i> and <i>container adapters</i>. The sequence containers and associative containers are collectively referred to as the <i>first-
class containers</i>. </indent>
<indent width=8 delay>* Four other types are considered "near containers"
because they exhibit similar capabilities to the first-
class containers, but do not support all the capabilities
of first-class containers--array, <b>string</b>, <b>bitset</b> and <b>valarray</b>. </indent>
<indent width=8 delay>* A <b>vector</b> provides rapid insertion and deletion at the
back of the <b>vector</b> and direct access to any element.
<b>vectors</b> support random-access iterators.</indent>
</page>
<page>
<indent width=8 delay>* A <b>deque</b> provides rapid insertion and deletion at the
front or back of the <b>deque</b> and direct access to any element. <b>deques</b> support random-access iterators.</indent>
<indent width=8 delay>* A <b>list</b> provides rapid insertion and deletion anywhere
in the <b>list</b>. <b>lists</b> support bidirectional iterators.</indent>
<indent width=8 delay>* A <b>set</b> provides rapid lookup of a key. No duplicate
keys are allowed. <b>sets</b> support bidirectional iterators.</indent>
<indent width=8 delay>* A <b>multiset</b> provides rapid lookup of a key. Duplicate
keys are allowed. <b>multisets</b> support bidirectional iterators.</indent>
<indent width=8 delay>* A <b>map</b> provides rapid lookup of a key and its corresponding "mapped" value. No duplicate keys are
allowed (i.e., a one-to-one mapping). <b>maps</b> support </indent>
<indent width=8 delay>* Iterators are used with sequences that may be in con</indent>
</page>
<page>
<indent width=8 delay>* tainers, or may be input sequences or output sequences. </indent>
<indent width=8 delay>* Input iterators are used to read an element from a
container. An input iterator can move only in the forward direction (i.e., from the beginning of the container
to the end of the container) one element at a time. Input
iterators support only one-pass algorithms.</indent>
<indent width=8 delay>* Output iterators are used to write an element to a
container. An output iterator can move only in the forward direction one element at a time. Output iterators
support only one-pass algorithms.</indent>
<indent width=8 delay>* Forward iterators combine the capabilities of input
and output iterators. Forward iterators support multi-
pass algorithms.</indent>
</page>
<page>
<indent width=8 delay>* Bidirectional iterators combine the capabilities of a
forward iterator with the ability to move in the backward direction.</indent>
<indent width=8 delay>* Random-access iterators combine the capabilities of
a bidirectional iterator with the ability to directly access
any element of the container, i.e., to jump forward or
backward by an arbitrary number of elements.</indent>
<indent width=8 delay>* The category of iterator supported by each container
determines whether that container can be used with specific algorithms in the STL. Containers that support
random-access iterators can be used with all algorithms
in the STL. </indent>
<indent width=8 delay>* Pointers into arrays may be used in place of iterators </indent>
</page>
<page>
<indent width=8 delay>* in all STL algorithms.</indent>
<indent width=8 delay>* STL includes approximately 70 standard algorithms.
Mutating-sequence algorithms result in modifications
to container elements. Non-mutating sequence algorithms do not modify the container elements.</indent>
<indent width=8 delay>* Functions <b>fill</b> and <b>fill_n</b> set every element in a range
of container elements to a specific value.</indent>
<indent width=8 delay>* Functions <b>generate</b> and <b>generate_n</b> use a <i>generator
function</i> to create values for every element in a range of
container elements. </indent>
<indent width=8 delay>* Function <b>equal</b> compares two sequences of values
for equality.</indent>
<indent width=8 delay>* Function <b>mismatch</b> compares two sequences of val</indent>
</page>
<page>
<indent width=8 delay>* ues and returns a <b>pair</b> of iterators indicating the location in each sequence of the mismatched elements. If all
the elements match, the <b>pair</b> contains the result of function <tt><b>end</b></tt> for each sequence. </indent>
<indent width=8 delay>* Function <b>lexicographical_compare</b> compares the
contents of two sequences to determine if one sequence
is less than another sequence (similar to a string comparison).</indent>
<indent width=8 delay>* Functions <b>remove</b> and <b>remove_copy</b> delete all elements in a sequence that match a specified value. Functions <b>remove_if</b> and <b>remove_copy_if</b> delete all
elements in a sequence for which the unary predicate
function passed to the functions returns <b>true</b>.</indent>
</page>
<page>
<indent width=8 delay>* Functions <b>replace</b> and <b>replace_copy</b> replace with a
new value all elements in a sequence that match a specified value. Functions <b>replace_if</b> and <b>replace_copy_if</b>
replace with a new value all elements in a sequence for
which the unary predicate function passed to the functions returns <b>true</b>.</indent>
<indent width=8 delay>* Function <b>random_shuffle</b> randomly orders the elements in a sequence.</indent>
<indent width=8 delay>* Function <b>count</b> counts the elements with the specified value in a sequence. Function <b>count_if</b> counts the
elements in a sequence for which the supplied unary
predicate function returns <b>true</b>.</indent>
<indent width=8 delay>* Function <b>min_element</b> locates the smallest element </indent>
</page>
<page>
<indent width=8 delay>* in a sequence. Function <b>max_element</b> locates the largest element in a sequence.</indent>
<indent width=8 delay>* Function <b>accumulate</b> sums the values in a sequence.
A second version of this function receives a pointer to a
general function that takes two arguments and returns a
result. The general function determines how the elements in a sequence are accumulated.</indent>
<indent width=8 delay>* Function <b>for_each</b> applies a general function to
every element in a sequence. The general function takes
one argument (that it should not modify) and returns
<b>void</b>.</indent>
<indent width=8 delay>* Function <b>transform</b> applies a general function to
every element in a sequence. The general function takes </indent>
</page>
<page>
<indent width=8 delay>* one argument (that it can modify) and returns the <b>transformed</b> result.</indent>
<indent width=8 delay>* Function <b>find</b> locates an element in a sequence and,
if the element is found, returns an iterator to the element; otherwise, <b>find</b> returns an iterator indicating the
end of the sequence. Function <b>find_if</b> locates the first
element for which the supplied unary predicate function
returns <b>true</b>.</indent>
<indent width=8 delay>* Function <b>sort</b> arranges the elements in a sequence in
sorted order (ascending order by default or in the order
indicated by a supplied binary predicate function).</indent>
<indent width=8 delay>* Function <b>binary_search</b> determines if an element is
in a sorted sequence.</indent>
</page>
<page>
<indent width=8 delay>* Function <b>swap</b> exchanges two values. </indent>
<indent width=8 delay>* Function <b>iter_swap</b> exchanges two values referred to
by iterators. </indent>
<indent width=8 delay>* Function <b>swap_ranges</b> exchanges the elements in
one sequence with the elements in another sequence.</indent>
<indent width=8 delay>* Function <b>copy_backward</b> copies elements in a
sequence and places the elements in another sequence
starting from the last element in the second sequence
and working toward the beginning of the second
sequence.</indent>
<indent width=8 delay>* Function <b>merge</b> combines two sorted ascending
sequences of values into a third sorted ascending
sequence. Note that <b>merge</b> also works on unsorted </indent>
</page>
<page>
<indent width=8 delay>* sequences, but does not produce a sorted sequence in
that case.</indent>
<indent width=8 delay>* A <b>back_inserter</b> uses the container's default capability for inserting an element at the end of the container. When an element is inserted into a container that
has no more elements available, the container automatically grows in size. There are two other inserters--
<b>front_inserter</b> and <b>inserter</b>. A <b>front_inserter</b> inserts
an element at the beginning of a container (specified as
its argument) and an <b>inserter</b> inserts an element before
the iterator supplied as its second argument in the container supplied as its first argument.</indent>
<indent width=8 delay>* Function <b>unique</b> removes all duplicates from a </indent>
